package com.wtgroup.demo.mianshi.算法.动态规划;

import org.junit.Test;

/**
 * 1 2 3 5 8 13 ...
 *
 * f(0)=f(1)=1
 * n>=2: f(n) = f(n-1) + f(n-2)
 *
 * @author 60906
 * @date 2021/5/12 10:28
 */
public class D_斐波那契数列 {
    @Test
    public void foo1() {
        // 打印出一段
        int len = 20;
        for (int i = 0; i < len; i++) {
            System.out.print(new Solution_1().process(i) + ", ");
        }
        System.out.println();
        for (int i = 0; i < len; i++) {
            System.out.print(new Solution_2().process(i) + ", ");
        }
        System.out.println();
        for (int i = 0; i < len; i++) {
            System.out.print(new Solution_3().process(i) + ", ");
        }

    }


    /**
     * M1: 暴力递归
     */
    class Solution_1 {
        int process(int n) {
            if (n < 2) {
                return 1;
            }
            return process(n - 1) + process(n - 2);
        }
    }

    /**
     * M2: 自顶向下动态规划(备忘录)
     *
     * 由暴力递归改造.
     */
    class Solution_2 {
        int[] dp = new int[1 << 10]; // 给一个差不多大数组缓存

        int process(int n) {
            if (dp[n] > 0) {
                // 备忘录已有, 直接返回
                return dp[n];
            }
            if (n < 2) {
                return 1;
            }
            return dp[n] = process(n - 1) + process(n - 2);
        }
    }

    /**
     * M3: 自底向上动态规划(无需备忘录)
     *
     * 自顶向下的动归, 需要多次递归调用和"试探", 试探意思是说, 递归看看缓存里有没有, 没有返回.
     * 分析可以看出, 下层无论如何都需要计算的, 与其浪费力气递归"试探", 不如提前都算好. 要的时候, 直接拿.
     * 备忘录式动归主要有两个缺点:
     * 1) 递归调用本身带来的开销; 2) 很多无效"试探".
     */
    class Solution_3 {
        int process(int n) {
            if (n < 2) {
                return 1;
            }
            int[] dp = new int[n + 1];
            dp[0] = dp[1] = 1;

            for (int i = 2; i <= n; i++) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }

            return dp[n];
        }
    }
}
